/*public class test {
}*/
public class QuickSort {
    // 分区操作：返回基准值最终索引
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 选最右侧元素为基准值（简单实现，优化可随机选）
        int i = left - 1; // i：小于基准值区域的右边界

        // 遍历数组，将≤基准值的元素移到左侧
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                // 交换i和j位置元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准值放到最终位置（i+1）
        int temp = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp;

        return i + 1; // 返回基准值索引
    }

    // 递归分治：分区+排序
    private static void sort(int[] arr, int left, int right) {
        if (left >= right) return; // 基线条件

        int pivotIndex = partition(arr, left, right); // 分区，获取基准值索引
        sort(arr, left, pivotIndex - 1); // 左半区排序（≤基准值）
        sort(arr, pivotIndex + 1, right); // 右半区排序（≥基准值）
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        sort(arr, 0, arr.length - 1);
        System.out.print("快速排序结果：");
        for (int num : arr) System.out.print(num + " "); // 输出：1 2 3 4 5 6 7 8
    }
}